<head>
    <meta charset="UTF-8">
<title>历届试题 九宫重排</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p>&nbsp; &nbsp; 如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。</p>
<p><img src="http://lx.lanqiao.cn/RequireFile.do?fid=qYebaGed" width="236" height="245" alt="" /><img src="http://lx.lanqiao.cn/RequireFile.do?fid=HQ3JFM72" width="236" height="245" alt="" /></p>
<p>&nbsp; &nbsp; 我们把第一个图的局面记为：12345678.</p>
<p>&nbsp; &nbsp; 把第二个图的局面记为：123.46758</p>
<p>&nbsp; &nbsp; 显然是按从上到下，从左到右的顺序记录数字，空格记为句点。</p>
<p>&nbsp; &nbsp; 本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。</p>
<p>【输入格式】</p>
<p>输入第一行包含九宫的初态，第二行包含九宫的终态。</p>
<p>【输出格式】<br />
输出最少的步数，如果不存在方案，则输出-1。</p>
<p>【样例输入】</p>
<p>12345678.</p>
<p>123.46758</p>
<p>【样例输出】</p>
<p>3</p>
<div>
<p>【样例输入】</p>
<p>13524678.</p>
<p>46758123.</p>
<p>【样例输出】</p>
<p>22</p>
</div>
<div>&nbsp;</div>